/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: Lenovo
 * Date: 2025-04-24
 * Time: 23:42
 */
public class MyLinkedList {

    // 定义双向链表的节点类
    static class ListNode {
        public int val;          // 节点存储的值
        public ListNode prev;    // 指向前一个节点的指针
        public ListNode next;    // 指向后一个节点的指针

        public ListNode(int val) { // 构造函数，初始化节点值
            this.val = val;
        }
    }

    public ListNode head; // 链表的头节点
    public ListNode last; // 链表的尾节点

    // 头插法：在链表头部插入新节点
    public void addFirst(int data) {
        ListNode node = new ListNode(data);
        if (head == null) { // 如果链表为空，新节点是头也是尾
            head = node;
            last = node;
        } else { // 否则将新节点插入到头部
            node.next = head;
            head.prev = node;
            head = node;
        }
    }

    // 尾插法：在链表尾部插入新节点
    public void addLast(int data) {
        ListNode node = new ListNode(data);
        if (head == null) { // 链表为空时，新节点是头也是尾
            head = last = node;
        } else { // 否则插入到尾部
            last.next = node;
            node.prev = last;
            last = node;
        }
    }

    // 在指定位置插入节点（从0开始计数）
    public void addIndex(int index, int data) {
        if (index < 0 || index > size()) return; // 索引越界检查
        if (index == 0) {
            addFirst(data); // 插入头部
            return;
        }
        if (index == size()) {
            addLast(data); // 插入尾部
            return;
        }
        ListNode cur = searchIndex(index); // 找到索引位置的节点
        ListNode node = new ListNode(data);
        // 调整指针将新节点插入到cur前
        node.next = cur;
        cur.prev.next = node;
        node.prev = cur.prev;
        cur.prev = node;
    }

    // 辅助方法：找到索引位置的节点
    private ListNode searchIndex(int index) {
        ListNode cur = head;
        int count = 0;
        while (count != index) { // 遍历到目标索引
            cur = cur.next;
            count++;
        }
        return cur;
    }

    // 检查链表中是否包含值为key的节点
    public boolean contains(int key) {
        ListNode cur = head;
        while (cur != null) { // 遍历链表
            if (cur.val == key) return true;
            cur = cur.next;
        }
        return false;
    }

    // 返回链表的长度
    public int size() {
        int count = 0;
        ListNode cur = head;
        while (cur != null) { // 遍历计数
            count++;
            cur = cur.next;
        }
        return count;
    }

    // 打印链表所有节点的值
    public void display() {
        ListNode cur = head;
        while (cur != null) {
            System.out.print(cur.val + " ");
            cur = cur.next;
        }
        System.out.println();
    }

    // 删除第一个值为key的节点
    public void remove(int key) {
        ListNode cur = head;
        while (cur != null) {
            if (cur.val == key) {
                if (cur == head) { // 删除头节点
                    head = head.next;
                    if (head != null) {
                        head.prev = null; // 更新新头节点的prev
                    } else {
                        last = null; // 链表为空，更新last
                    }
                } else {
                    cur.prev.next = cur.next; // 修改前驱节点的next
                    if (cur.next == null) { // 删除尾节点
                        last = cur.prev; // 更新尾节点
                    } else {
                        cur.next.prev = cur.prev; // 修改后继节点的prev
                    }
                }
                return; // 只删除第一个匹配的节点
            }
            cur = cur.next;
        }
    }

    // 删除所有值为key的节点
    public void removeAllKey(int key) {
        ListNode cur = head;
        while (cur != null) {
            if (cur.val == key) {
                if (cur == head) { // 处理头节点
                    head = head.next;
                    if (head != null) {
                        head.prev = null;
                    } else {
                        last = null;
                    }
                } else {
                    cur.prev.next = cur.next; // 修改前驱节点的next
                    if (cur.next == null) { // 处理尾节点
                        last = cur.prev;
                    } else {
                        cur.next.prev = cur.prev; // 修改后继节点的prev
                    }
                }
            }
            cur = cur.next; // 继续遍历
        }
    }

    // 清空链表
    public void clear() {
        ListNode cur = head;
        while (cur != null) { // 遍历所有节点，断开链接
            ListNode curNext = cur.next;
            cur.next = null;
            cur.prev = null;
            cur = curNext;
        }
        head = last = null; // 重置头尾节点
    }
}